import org.junit.Test

//给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
//
// 
//
// 
// 
//
// 示例 1: 
//
// 输入: amount = 5, coins = [1, 2, 5]
//输出: 4
//解释: 有四种方式可以凑成总金额:
//5=5
//5=2+2+1
//5=2+1+1+1
//5=1+1+1+1+1
// 
//
// 示例 2: 
//
// 输入: amount = 3, coins = [2]
//输出: 0
//解释: 只用面额2的硬币不能凑成总金额3。
// 
//
// 示例 3: 
//
// 输入: amount = 10, coins = [10] 
//输出: 1
// 
//
// 
//
// 注意: 
//
// 你可以假设： 
//
// 
// 0 <= amount (总金额) <= 5000 
// 1 <= coin (硬币面额) <= 5000 
// 硬币种类不超过 500 种 
// 结果符合 32 位符号整数 
// 
// 👍 514 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class SolutionChange {
    @Test
    fun test() {
        println(change(5, intArrayOf(1, 2, 5)))
        // println(change(3, intArrayOf(2)))
        // println(change(10, intArrayOf(10)))
        // println(change(1000, intArrayOf(3,5,7,8,9,10,11)))
    }

    fun change(amount: Int, coins: IntArray): Int {
        // return getCount(amount, coins, 0)
        // return getCountByPackage(amount, coins)
        return getCountByPackage(amount, coins)
    }
    // private int getCountByPackage1(int amount, int[] coins) {
    //     return 0;
    // }

    /***
     * 对于面额为 coin\textit{coin}coin 的硬币，当 coin≤i≤amount\textit{coin} \le i \le \textit{amount}coin≤i≤amount 时，如果存在一种硬币组合的金额之和等于 i−coini - \textit{coin}i−coin，则在该硬币组合中增加一个面额为 coin\textit{coin}coin 的硬币，即可得到一种金额之和等于 iii 的硬币组合。因此需要遍历 coins\textit{coins}coins，对于其中的每一种面额的硬币，更新数组 dp\textit{dp}dp 中的每个大于或等于该面额的元素的值。

    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode-soluti-f7uh/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    private fun getCountByPackage(amount: Int, coins: IntArray): Int {
        // val dp = Array(coins.size + 1) { IntArray(amount + 1) }
        val dp = IntArray(amount + 1)
        dp[0] = 1;
        // 假定 coin 是有序排列的
        for (coin in coins) {
            for (i in coin..amount) {
                dp[i] += dp[i - coin]
            }
        }
        return dp[amount]
    }

    /**
     * 计算{@code coins}中从{@code left}开始，开始组合成{@code amount}的个数
     */
    private fun getCount(amount: Int, coins: IntArray, left: Int): Int {
        // TODO("Not yet implemented")
        if (left >= coins.size) {
            return 0
        }
        if (left == coins.size - 1) {
            if (amount % coins[left] == 0) {
                return 1
            } else {
                return 0
            }
        }
        val iCount = amount / coins[left]
        var count = 0
        for (i in 0..iCount) {
            count += getCount(amount - coins[left] * i, coins, left + 1)
        }
        return count
    }
}
//leetcode submit region end(Prohibit modification and deletion)
